\section{Lower bound}
\label{sec:lowerbound}

\iffalse

\danupon{The first part is to be integrated to the rest of this
section.}

\begin{definition}[Natural Random Walk Algorithms]\label{def:natural
algo}\danupon{I'd prefer other name as this will make it sounds like
the great ``natural proofs'' result too much.} A random walk
algorithm is {\em natural} if it satisfies the following conditions.
First, recall that in the beginning, the source node $s$ knows the
length $\ell$ of the walk it wants to perform. We say that $s$ owns
an interval $[1, \ell]$. Now, for each round $r$, each node $v$
owning an interval $[i, j]$ can do the following. (Note that each
node can own more than one interval.)
%
First, $v$ can send a subinterval $[i', j']\subseteq [i, j]$ to its
neighbor. Each edge can have only one interval sent
through it per round. Moreover, if a node $v$ sends an interval $[i', j']$ to
some neighbor in round $r$ then $v$ can delete any numbers in $[i',
j']$ in this round (thus, it does not own such numbers anymore). At
the time the algorithm terminates, for each number $i$ in $[1,
\ell]$ there must be only one node, denoted by $v_i$, that owns $i$.
The output random walk is $s=v_1, v_2, \ldots, v_\ell$.
\end{definition}


{\bf Motivation:}\danupon{To be polished if we will keep this.} What
can a random walk algorithm do? In the beginning, only the source
node knows the length of the walk $\ell$. Then, it might ask other
nodes to help finding pieces of the walk; i.e., send intervals which
refer to pieces of the walk to those nodes.


Definition of Path Verification Problem: ..,.

We claim that any natural random walk algorithm using $f(\ell, D,
n)$ rounds can be converted to an algorithm that solves the Path
Verification Problem in $O(f(\ell, D, n))$ rounds as follows. ...
State the theorem now.

------------------------------------------------------------------------------------

Gopal -- I commented the above, as it is confusing to define this
class for the random walk problem. Better to do this for the path
verification and then connect it to random walk, as I attempt to do
below. \fi

In this section, we show an almost tight lower bound on the time
complexity of performing a distributed random walk. At the end of the walk,
we require that each node in the walk should know its correct position(s) among the $\ell$ steps.
%s, i.e., specifically for the {\em Single Random Walk} problem.
We show that any distributed algorithm needs  at least
$\Omega\left(\sqrt{\frac{\ell}{\log \ell}}\right)$ rounds, even in
graphs with low diameter. Note that $\Omega(D)$ is a  lower bound
\cite{DNP09-podc}. Also note that if a source node wants to sample
$k$ destinations from independent random walks, then $\Omega(k)$ is
also a lower bound as the source may need to receive $\Omega(k)$
distinct messages. Therefore, for $k$ walks, the lower bound we show
is $\Omega(\sqrt{\frac{\ell}{\log \ell}} + k + D)$ rounds.
%For small diameter graphs, this almost matches our upper bound for $k=1$.
(The rest of the section omits the $\Omega(k+D)$ term.) In particular, we
show that there exists a $n$-node graph of diameter $O(\log n)$ such
that any distributed algorithm needs at least
$\Omega(\sqrt{\frac{n}{\log n}})$ time to perform a walk of length
$n$. Our lower bound proof makes use of a lower bound for another
problem that we call as the {\em Path Verification problem} defined
as follows. Informally, the Path Verification problem is for
some node $v$ to verify that a
given sequence of nodes in the graph is a valid path of length $\ell$.

\begin{definition}[{\sc Path-Verification} Problem]
The input of the problem consists of an integer $\ell$, a graph $G =
(V,E)$, and $\ell$  nodes $v_1, v_2, ...,
v_\ell$ in $G$. To be precise, each node $v_i$ initially has its
order number $i$.

The goal is for some node $v$ to ``verify" that the above sequence
of vertices forms an $\ell$-length path, i.e., if
$(v_i,v_{i+1})$ forms an edge for all $1 \leq i \leq \ell - 1$.
Specifically, $v$ should output ``yes" if the sequence forms an $\ell$-length
path and ``no" otherwise.
\end{definition}


%\gopal{Better to Capitalize "P" and "V" in Path Verification
%throughout.}

We show a lower bound for the Path Verification problem that applies
to a very general class of verification algorithms defined as follows.
%Each node can (only) send a segment of the path that it can verify
%either directly or indirectly (by learning from its neighbors), as
%follows.
% Initially, each node $v_i$ verify its own position, i.e., it
%verifies the number $i$. In each of the later rounds, each node $u$
%can send the numbers it has verified to its neighbors. Note that the
%numbers can be sent in ``chunks''; i.e., if a node has verified
%numbers $i, i+1, \ldots, j$ then it can simply send an interval $[i,
%j]$ to its neighbors. However, in each round only one chunk
%(interval) of numbers can be sent through each edge. Once a node
%receives an interval $[i, j]$ from its neighbor, we say that it has
%verified the number $i, i+1, \ldots, j$ as well.(See Figure~\ref{fig:path_verify_definition} in Appendix)
%The goal of the problem is that, in the end, some node verifies all
%numbers $1, 2, \ldots, \ell$.
Each node can (only) verify a segment of the path that it knows
either directly or indirectly (by learning form its neighbors), as
follows.
%
Initially each node knows only the trivial segment (i.e. the vertex
itself). If a vertex obtains from its neighbor a segment $[i_1,j_1]$
and it has already verified segment $[i_2,j_2]$ that overlaps with
$[i_1, j_1]$ (say, $i_1 < i_2 < j_1 < j_2$) then it can verify a
larger interval ($[i_1,j_2]$). Note that a node needs to only send
the endpoints of the interval that it already verifies (hence larger
intervals are better). The goal of the problem is that, in the end,
some node verifies the entire segment $[1,\ell]$. We would like to
determine a lower bound for the running time of any distributed
algorithm for the above problem.

%\begin{figure}[h]
%\centering
%\includegraphics{path_verify_definition.eps}
%\caption{\footnotesize{Example of path verification problem. {\bf (a)} In the
%beginning, we want to verify that the vertices containing numbers
%$1..5$ form a path. (In this case, they form a path $a, b, c, d,
%a$.) {\bf (b)} One way to do this is for $a$ to send $1$ to $b$ and
%therefore $b$ can check that two vertices $a$ and $b$ corresponds to
%label $1$ and $2$ form a path. (The interval $[1,2]$ is used to
%represent the fact that vertices corresponding to numbers $1, 2$ are
%verified to form a path.) Similarly, $c$ can verify $[3,5]$. {\bf
%(c)} Finally, $c$ combine $[1,2]$ with $[3, 5]$ and thus the path
%corresponds to numbers $1,2, ..., 5$ is verified. }}
%\label{fig:path_verify_definition}
%\end{figure}


\iffalse
\danupon{I remove the following paragraph as it seems redundant\\
The Path Verification problem can be thought of as follows.
Initially, each node $v_i$ knows its order number $i$ and they want
to together ``verify'' that $v_1, v_2, \ldots, v_\ell$ is indeed a
path.
%
In other words, the goal of the path verification problem is for
some node $v$ to obtain a ``certificate" that verifies that the
given sequence of nodes is a valid path of length $\ell$.
%
Each node can (only) verify a segment of the path that it knows
either directly or indirectly (by learning form its neighbors), as
follows.
%
Initially each node knows only the trivial segment itself. If a
vertex obtains from its neighbor a segment $[i_1,j_1]$ and it has
already verified segment $[i_2,j_2]$ that overlaps with $[i_1, j_1]$
(say, $i_1 < i_2 < j_1 < j_2$) then it can verify a larger interval
($[i_1,j_2]$). Note that a node needs to only send the endpoints of
the interval that it already verifies (hence larger intervals are
better). We would like to determine a lower bound for the running
time of any distributed algorithm for the above problem.} \fi

%\danupon{I think we should remove this paragraph and put a formal
%statement instead. Need to discuss first.}


A lower bound for the
Path Verification problem, implies a lower bound for the random walk
problem as well.
 The reason is as follows.
Both problems involve
constructing  a path of some specified length $\ell$. Intuitively,
the former is a simpler problem, since we  are not verifying whether
the local steps are chosen randomly, but just whether the path is
valid and is of length $\ell$. On the other hand, any algorithm for
the random walk problem (including our algorithm of Section
\ref{sec:one_walk_DoS}), also solves the Path Verification problem,
since the path it constructs should be a valid path of length
$\ell$.
It is straightforward to make any distributed algorithm that
computes a random walk  to also verify that  indeed the random walk
is a valid walk of appropriate length.  This is essential for
correctness, as otherwise, an adversary can always change  simply
one edge of the graph and ensure that the walk is wrong.

\iffalse
We formalize this intuition below.

\begin{definition}[Single Random Walk  With Token Distribution Problem]\label{def:natural
algo} In this problem, we are
given a  source node $s$, a graph $G = (V,E)$, and  $s$
is given $\ell$ tokens numbered from $1$ to $\ell$. The goal is
for $s$ is to distribute the tokens such that token $i$ ends up at
the $i$th node in a $\ell$-length random walk generated from $s$.
In one round, a node can send a subset of of tokens that it owns to its neighbor. Initially $s$ owns all the $\ell$ tokens. Sending one token across
and edge
takes $O(\log \ell)$ bits. Also sending a bunch of successively numbered tokens
(an interval) also takes only $O(\log \ell)$ bits as only the endpoints has to be sent through the edge. However, sending tokens from $k$ disjoint intervals will take $O(k \log \ell)$ bits.
\end{definition}

We  show in Section \ref{sec:reduction}
that we can reduce Path Verification to Single Random Walk.


\begin{lemma}
Given an algorithm  for the Single Random Walk with Token Distribution
that runs in $T$ rounds, we can construct an algorithm to solve the Path Verification Problem in $O(T)$ rounds with high probability.
\end{lemma}


\begin{proof}
Let $v_1,v_2, \dots, v_{\ell}$ be the sequence of vertices input to
the Path Verification problem in a given graph $G$. We now construct a modified graph $G'$ from $G$ as follows: If $(v_i,v_{i+1}) is an edge in $G$, we add a ``large" number of multiple edges between each $(v_i, v_{i+1})$ (in other words,
give a large weight to this edge), otherwise (if there is no edge)
then we do nothing. By choosing the weight sufficiently large, we can force
the random walk to choose the path $v_1,v_2, \dots$ with probability (if it exists). Then the tokens will  be distributed correctly.
\end{proof}
\fi


%\gopal{I wrote the above --- it appears in the tex file only, but
%then commented it, it is basically the same as the reduction, but it
%seems that we are unnecessarily formalizing it, at least in this
%extended abstract. Better to leave it as it is, I think.}

In the next section we first prove a lower bound for the Path
Verification problem. Then we show the same lower bound holds for the
random walk  problem by giving a reduction.

\subsection{Lower Bound for the Path Verification Problem}

The main result of this section is the following theorem.
\begin{theorem}
\label{thm:mainLB} For every $n$, and $\ell \leq n$ there exists a
graph $G_n$ of $\Theta(n)$ vertices and diameter $O(\log n)$, and a
path $P$ of length $\ell$ such that any algorithm  that solves the
{\sc Path-Verification} problem on $G_n$ and $P$ requires more than
$k$ rounds, where $k=\sqrt{\frac{\ell}{\log \ell}}$.
\end{theorem}


The rest of the section is devoted to proving the above Theorem. We
start by defining $G_n$.

\begin{definition}[Graph $G_{n}$] Let $k'$ be an integer such that
$k$ is a power of $2$ and $k'/2\leq 4k < k'$. Let $n'$ be such that
$n'\geq n$ and $k'$ divides $n'$. We construct $G_n$ having
$(n'+2k'-1)=O(n)$ nodes as follows. First, we construct a path
$P=v_1v_2...v_{n'}$. Second, we construct a binary $T$ having $k'$
leaf nodes. Let $u_1, u_2, ..., u_{k'}$ be its leaves from left to
right. Finally, we connect $P$ with $T$ by adding an edge
$u_iv_{jk'+i}$ for every $i$ and $j$. We will denote the root of $T$
by $x$ and its left and right children by $l$ and $r$ respectively.
Clearly, $G_n$ has diameter $O(\log n)$. We then consider a path of
length $\ell=\Theta(n)$. If required $n$ can always be made larger
by connecting dummy vertices to the root of $T$.(The resulting graph
$G_n$ is as in Figure~\ref{fig:graph_construction}.) \qed
\end{definition}


%{\bf Gopal;} It wil be good to make the figures more clearer, larger if possible. We
%can try to put figures side by side to gain space.
%Explanations in Figure 4 and 5 have to be fixed for style.
%{\bf Danupon:} The figure could be larger by changing the width below (in the includegraphics ...).
%I've changed the picture a bit. I don't know what else to do to make it clearer.

%**********************************************************
\begin{figure}
  \centering
  \includegraphics[width=0.7\linewidth]{Graph_Construction.eps}\\
  \caption{$G_n$}\label{fig:graph_construction}
\end{figure}
%**********************************************************


To prove the theorem, let $\mathcal A$ be any algorithm for the {\sc
Path-Verification} problem that solves the problem on $G_n$ in at
most $k'$ rounds. We need some definitions and claims to prove the
 theorem.


%(GOPAL --- It will be good to put all proofs of the lower bound in
%the main paper. It won't increase the space by too much and it will
%read much better.)



\paragraph{\bf Definitions of {\em left/right subtrees} and {\em
breakpoints}.}

%{\bf Gopal:} In he definition of subtrees below, we have to make it clear that the subtree includes
%the nodes in the path also. Note that the graph is not tree if it includes the path, as there are cycles.
%We have to just clarify this.

%{\bf Danupon:} I added one more sentence. Hope it is clear now.

%Let the root $x$'s two neighbors be $r$ and $l$ (for right and left
%children respectively).

Consider a tree $T'$ obtained by deleting all edges in $P$. Notice
that nodes $v_{jk'+i}$, for all $j$ and $i \leq k'/2$ are in the
subtree of $T'$ rooted at $l$ and all remaining points are in the
subtree rooted at $r$. For any node $v$, let $sub(v)$ denote the
subtree rooted at node $v$. (Note that $sub(v)$ also include nodes
in the path $P$.) We denote the set of nodes that are leaves of
$sub(l)$ by $L$ (i.e., $L=sub(l)\cap P$) and the set of nodes that
are leaves in $sub(r)$ by $R$.

%{\bf Gopal:} I think it should be $k'$ in the first line below instead of $k$.
%Also carefully check the notations below, in particular, should it be " $v_{jk'+k+1}$"
%in the last line of the para below.

{%\bf Danupon:} $k$ in the first line is correct. I changed the sentence a bit. Hope it is clearer.
%Yes, it should be ``$v_{jk'+k+1}$" in the last line.


Since we consider an algorithm that takes at most $k$ rounds,
consider the situation when the algorithm is given $k$ rounds for
{\em free} to communicate only along the edges of the path $P$ at
the beginning.
%
Since $L$ and $R$ consists of every $k'/2$ vertices in $P$ and
$k'/2> 2k$, there are some nodes unreachable from $L$ by walking on
$P$ for $k$ steps. In particular, all nodes of the form
$v_{jk'+k'/2+k+1}$, for all $j$, are not reachable from $L$. We call
such nodes {\em breakpoints} for $sub(l)$. Similarly all nodes of
the form $v_{jk'+k+1}$, for all $j$, are not reachable from $R$ and
we call them the breakpoints for $sub(r)$.


%Let any
%node in $P$ that is not reachable from $L$ (i.e., $v_{jk'+k'/2+i}$,
%for all $j$ and $k < i < k'/2-k$) in the initial $k$ rounds be
%called a {\em breakpoint} for $sub(l)$. Similarly, any node that is
%not reachable from vertices in $R$ be called a {\em breakpoint} for
%$sub(r)$. In particular, all nodes of the form $v_{jk'+k'/2+k+1}$,
%for all $j$, are breakpoints for $sub(l)$. Let $B_l$ be the set of
%such nodes. Similarly all nodes of the form $v_{jk'+k+1}$, for all
%$j$ are breakpoints for $sub(r)$ and we let $B_r$ be the set of
%such nodes. (See Figure~\ref{fig:breaking-points}.)

%***********************************************************
%\begin{figure}
%\centering
%\includegraphics{breaking-points.eps}
%\caption{\textbf{Breakpoints.} {\bf (a)} $L$ and $R$ consist of every other $k'/2$ vertices in $P$.
%(Note that we show the vertices $l$ and $r$ appear many times for the convenience of presentation.)
%{\bf (b)} $v_{k'/2+k+1}$ and $v_{k'+k'/2+k+1}$ (nodes in black) are two of the breakpoints for $L$.
%Notice that there is one breakpoint in every connected piece of $L$ and $R$.} \label{fig:breaking-points}
%\end{figure}
%***********************************************************

\paragraph{\bf Definitions of {\em path-distance} and {\em
covering}.}


%{\bf Gopal:} Again, does the "number of leaves below" include the nodes on the path below"

%{\bf Danupon:} I added one more sentence and changed the picture to clarify this.

For any two nodes $u$ and $v$ in $T'$ (obtained from $G_n$ by
deleting edges in $P$), let $c(u, v)$ be a lowest common ancestor of
$u$ and $v$. We define $path\_dist(u, v)$ to be the number of leaves
of subtree of $T$ rooted at $c(u, v)$. Note that the path-distance
is defined between any pair of nodes in $G_n$ but the distance is
counted using the number of leaves in $T$ (which excludes nodes in
$P$).
%(Recall that $T$ does not contain vertices in $P$.)


%{\bf Gopal:} It is still confusing. When you say two nodes, they can also be nodes belonging to the path right?
%But then you are saying that $T$ does not include $P$.

%%*********************************************************
%\begin{figure}
%\centering
%\subfigure[{Path-distance.}]{
%\includegraphics[width=0.35\linewidth]{path-distance.eps}
%\label{fig:path_distance}}
%%
%\subfigure[{Idea of Claim~\ref{claim:one}}]{
%\includegraphics[width=0.35\linewidth]{scratch_4.eps}
%\label{fig:scratch_4}
%}
%%
%\subfigure[Idea of Lemma~\ref{lem:three}.]{
%\includegraphics[width=0.25\linewidth]{max_path_cover.eps}
%\label{fig:max_path_cover}
%}
%\caption{{\bf (a)} Path distance between 1 and 2 is the
%number of leaves in the subtree rooted at 3,
%the lowest common ancestor of 1 and 2. {\bf (b)} For one unscratched left breakpoint, $k'/2+k+1$
%to be combined with another right breakpoint
%$k+1$ on the left, $k'/2+k+1$ has to be carried
%to $L$ by some intervals.
%Moreover, one interval can carry at most two
%unscratched breakpoints at a time. {\bf (c)} Sending a message between nodes on level $i$ and $i-1$ can
%increase the covered path distance by at most $2^i$}
%\end{figure}
%%**********************************************************

%%*********************************************************
%\begin{figure*}
%\centering \subfigure[{Path-distance.}]{
%\includegraphics[width=0.35\linewidth]{path-distance.eps}
%\label{fig:path_distance}}
%%
%\subfigure[{Idea of Claim~\ref{claim:one}}]{
%\includegraphics[width=0.35\linewidth]{scratch_4.eps}
%\label{fig:scratch_4} }
%%
%\subfigure[Idea of Lemma~\ref{lem:three}.]{
%\includegraphics[width=0.25\linewidth]{max_path_cover.eps}
%\label{fig:max_path_cover} } \caption{{\bf (a)} Path distance
%between 1 and 2 is the number of leaves in the subtree rooted at 3,
%the lowest common ancestor of 1 and 2. {\bf (b)} For one unscratched
%left breakpoint, $k'/2+k+1$ to be combined with another right
%breakpoint $k+1$ on the left, $k'/2+k+1$ has to be carried to $L$ by
%some intervals. Moreover, one interval can carry at most two
%unscratched breakpoints at a time. {\bf (c)} Sending a message
%between nodes on level $i$ and $i-1$ can increase the covered path
%distance by at most $2^i$}
%\end{figure*}
%%**********************************************************

%\begin{figure}
%\center
%\includegraphics[width=0.3\linewidth]{path-distance.eps}
%\caption{{\bf Path-distance.} Path distance between 1 and 2 is the
%number of leaves in the subtree rooted at 3,
%the lowest common ancestor of 1 and 2.} \label{fig:path_distance}
%\end{figure}

%Let us define the {\em path-distance} between two nodes $v_i$ and
%$v_j$ in $P$ as the distance between $v_i$ and $v_j$ on the path
%$v_1, v_2, \ldots, v_n$. That is $path\_dist(v_i, v_j) = |i-j+1|$. We
%also define the path distance between any two nodes in the graph in
%a similar manner: $path\_dist(x,y)$ is computed as $2^j$ where $j$ is
%the level of the first common ancestor of $x$ and $y$.

We also introduce the notion of the path-distance {\em covered} by a
message. For any message $m$, the path-distance covered by $m$ is
the maximum path-distance taken over all nodes that have held the
message $m$. That is, if $m$ covers some nodes $v'_1, v'_2, ...,
v'_k$ then the path-distance covered by $m$ is the number of leaves
in the subtrees of $T$ rooted by $v'_1, v'_2, ..., v'_k$. Note that
some leaves may be in more than one subtrees and they will be
counted only once.
%
Our construction makes the right and left subtrees have a large
number of break points, as in the following lemma.
%
%For any message $m$, the path-distance covered by $m$ is
%the maximum path-distance taken over all pairs of nodes that have
%held the message $m$.

%{\bf Gopal:} The above is a bit confusing. Since nodes on a path also hold the message, we need
%the notion of path-distance between any two nodes. So I guess, we should define path distance in the tree
%T' (T + vertices of P - edges of P). I think this is what you mean. See my previous comment.
%{\bf Danupon:} I also asked the same question earlier. I've redefine it as above.
%\textbf{Danupon:} What does this mean?

\begin{lemma}
\label{lem:one} The number of breakpoints for the left subtree and
for the right subtree are at least $\frac{n}{4k}$ each.
\end{lemma}




The reason we define these breakpoints is to show that the entire
information held by the left subtree has many disjoint intervals,
and same for the right subtree. This then tells us that the left
subtree and the right subtree must {\em communicate} a lot to be
able to merge these intervals by connecting/communicating the break
points.
%
To argue this, we show that the total path distance (over all
messages) is large, as in the following lemma. (Proof is in the full
version~\cite{fullversion}.)

%{\bf Gopal:} The term $path\_dist$ looks a bit ugly. I would put underscore or omit hyphen altogether.

%{\bf Danupon:} It is now path\_dist

\begin{lemma}
\label{lem:two} For algorithm $\mathcal A$ to solve {\sc
Path-Verification} problem, the total path-distance covered by all
messages is at least $n$.
\end{lemma}



%REMOVE AND USE SUBFIG INSTEAD
%\begin{figure}
%\center
%\includegraphics[width=0.3\linewidth]{scratch_4.eps}
%\caption{{\bf Idea of Claim~\ref{claim:one}} For one unscratched left breakpoint, $k'/2+k+1$
%to be combined with another right breakpoint
%$k+1$ on the left, $k'/2+k+1$ has to be carried
%to $L$ by some intervals.
%Moreover, one interval can carry at most two
%unscratched breakpoints at a time.} \label{fig:scratch_4}
%\end{figure}

These messages can however be communicated using the tree edges as
well. We bound the maximum communication that can be achieved across
$sub(l)$ and $sub(r)$ indirectly by bounding the maximum
path-distance that can be covered in each round. In particular, we
show the following lemma. Proof is in the full
version~\cite{fullversion}.
%(proved in Appendix~\ref{proof:lem:three}).

\begin{lemma}
\label{lem:three} In $k$ rounds, all messages together can cover at
most a path-distance of $O(k^2\log k)$.
\end{lemma}
%\begin{proof}
%We consider the total number of messages that can go through nodes
%at any level of the graph, starting from level $0$ to level $\log k$
%under the congest model.

%First notice that if a message is passed at level $i$ of the tree,
%this can cover a $path\_dist$ of at most $2^i$. This is because the
%subtree rooted at a node at level $i$ has $2^i$ leaves. Further, by
%our construction, there are $2^{\log (k') - i}$ nodes at level $i$.
%Therefore, all nodes at level $i$ together, in a given round of
%$\mathcal A$ can cover a $dist-path$, path distance, of at most
%$2^i2^{\log (k') - i} = 4k+2$. Therefore, over $k$ rounds, the total
%$path\_dist$ that can be covered in a single level is $k(k')$. Since
%there are $O(\log k)$ levels, the total $path\_dist$ that can be
%covered in $k$ rounds over the entire graph is $O(k^2\log k)$.
%(See Figure~\ref{fig:max_path_cover}.)
%%
%% in the Appendix.)
%%
%\end{proof}

%MOVED TO SUBFIGURE
%\begin{figure}
%\center
%\includegraphics{max_path_cover.eps}
%\caption{\textbf{Idea of Lemma~\ref{lem:three}.} Sending a message between nodes on level $i$ and $i-1$ can
%increase the covered path distance by at most $2^i$} \label{fig:max_path_cover}
%\end{figure}

We now describe the proof of the main theorem using these three
claims.

\begin{proof} [of Theorem~\ref{thm:mainLB}]
Use Lemmas~\ref{lem:two} and~\ref{lem:three} we know that if
$\mathcal A$ solves {\sc Path-Verification}, then it needs to cover
a $path\_dist$ of $n$, but in $k$ rounds it can only cover a
$path\_dist$ of $O(k^2\log k)$. But this is $o(n)$ since
$k=\sqrt{\frac{n}{\log n}}$, contradiction.
\end{proof}

\iffalse We remark that the path verification problem can be solved
in $O(\sqrt{\ell} + D)$ rounds. The node that needs to verify the
path from $1$ to $n$ can ask node with id $i\sqrt{\ell}+1$ to verify
the path from $i\sqrt{\ell}$ to $(i+1)\sqrt{\ell}$, for all $0\leq
i\leq \sqrt{\ell}-1$. Each such piece can be verified in parallel,
in $O(\sqrt{\ell})$ rounds; this crucially uses the fact that the
path being verified is a simple path (i.e. no vertex/edge
repetitions) and the fact that it is numbered $1$ through $n$. In
case of random walks, there can be vertex repetitions; additionally,
the subsequent node ids of the walk steps are unknown. This is what
makes an upper bound for the random walk problem more involved. \fi

\subsection{Reduction to Random Walk Problem} \label{sec:reduction}
We now discuss how the lower bound for the Path Verification problem
implies the lower bound of the random walk problem. The main
difference between {\sc Path-Verification} problem and the random
walk problem is that in the former we can specify which path to
verify while the latter problem generates different path each time.
We show that the ``bad'' instance ($G_n$ and $P$) in the previous
section can be modified so that with high probability, the generated
random walk is ``hard'' to verify. The theorems below are stated for $\ell$ length walk/path instead of $n$ as above. As previously stated, if it is desired that $\ell$ be $o(n)$, it is always possible to add dummy nodes.




%{\bf Gopal}: Here we should discuss how the lower bound for the path verification
%implies a lower bound for a the random walk problem.  Just a short description how we can make a
%random walk can be made to walk the path of length $n$ in the above constructed graph (adding enough multiple
%edges to mimic weights). We can also point out that the same lower bound result will hold if the verification
%is done by starting point of the random walk (rather than the root).

%{\bf Danupon}: Is below enough? BTW, the path verification problem shouldn't specify that
%the path has to be verified by the root.


\begin{theorem}
For any $n$, there exists a graph $G_n$ of $\Theta(n)$ vertices and
diameter $O(\log n)$, and $\ell=\Theta(n)$ such that, with high
probability, a random walk of length $\ell$  needs
$\Omega(\sqrt{\frac{\ell}{\log \ell}})$  rounds.
\end{theorem}

\begin{proof}
Theorem~\ref{thm:mainLB} can be generalized to the
case where the path $P$ has infinite capacity, as follows.

\begin{theorem}
\label{thm:general-LB} For any $n$ and $\ell=\Theta(n)$, there exists a graph $G_n$ of
$O(n)$ vertices and diameter $O(\log n)$, and a path $P$ of length
$\ell$ such that any algorithm that solves the {\sc
Path-Verification} problem on $G_n$ and $P$ requires more than $\Omega(\sqrt{\frac{\ell}{\log \ell}})$
rounds, even if edges in $P$ have large capacity (i.e., one can send
larger sized messages in one step).
%, where $k=\sqrt{\frac{n}{\log n}}$.
\end{theorem}

\begin{proof}
This is because the proof of Theorem~\ref{thm:mainLB} only uses the
congestion of edges in the tree $T$ (imposed above $P$) to argue
about the number of rounds.
\end{proof}

Now, we modify $G_n$ to $G'_n$ as follows. Recall that the path $P$
in $G_n$ has vertices $v_1, v_2, ..., v_{n'}$. For each $i=1, 2,
..., n'$, we define the weight of an edge $(v_i,v_{i+1})$ to be
$(2n)^{2i}$ (note that weighted graphs are equivalent to unweighted
multigraphs in our model). By having more weight, these edges have
more capacity as well. However, increasing capacity does not affect
the claim as shown above. Observe that, when the walk is at the node
$v_i$, the probability of walk will take the edge $(v_i,v_{i+1})$ is
at least $1-\frac{1}{n^2}$. Therefore, $P$ is the resulting random
walk with probability at least $1-1/n$. When the random walk path is
$P$, it takes at least $\sqrt{\frac{n}{\log n}}$ rounds to verify,
by Theorem~\ref{thm:general-LB}. This completes the proof.
We remark that this construction requires exponential in $n$ number of edges (multiedges). %This does not take away anything from the lower bound as it is the distributed computing model where this only translates to allowing the algorithm a larger bandwidth.
For the distributed computing model, this only translates to a larger bandwidth.
The length $\ell$ is still comparable to the number of nodes.
%
%\textbf{Danupon:} The problem with the above proof is that the weights are really huge. So, we cannot call them multiple edge.
%One idea to fix this is to put only $2^i$ edges between $v_i$ and $v_{i+1}$ and argue that the walk will have length $\Omega(n)$ with
%high probability. Then, we need to modify the theorem to deal with paths of length, say $n/2$, as well. Is $2^n$ small enough?
%
%{\bf Gopal:} Why we cannot call them multiple edge (as I say in the proof above)? What is the differnece
%if the wieght is $2^i$ as opposed to $n^i$ ?
%{\bf Danupon:} My only worry is that $n^i$ is too much for the number of edges. (That's also true for $2^i$.)
%If you think it is fine then that is ok.
%
%Another idea is to only show that with constant probability that the path will be taken.
%Then our lower bound statement will hold with constant probability instead of high probablity.
%In this case, we need only polynomial weights -- $n^2$ will suffice for every edge in the path. Do you agree?
%If this is correct, we can state this also.
\end{proof}

%\atish{I added the below paragraph since in SODA some reviewer complained about this. But seems like this paragraph is too argumentative. Gopal, do you see a better way to state this? Or should we just drop this entire para and take a chance?}


%We would like to remark that the above reduction from Path Verification to random walk requires exponential in $n$ number of edges (multiedges). This does not take away anything from the lower bound as it is the distributed computing model where this only translates to allowing the algorithm a larger bandwidth. The length $\ell$ is still comparable to the number of nodes.
%In the local decentralized computation model, the size of the input is irrelevant.
\iffalse
\atish{In the LB section, do we still claim that our upper bound can in fact solve path verification? I had included this long back following Prasad's suggestion but can't find it now. If we do claim this, it is correct only for "simple path verification" - but when we define the path verification problem, we emphasize twice (I don't know why) that the vertices in the path are not necessarily distinct.}
\fi

%\subsection{Reduction to Random Walk Problem}
%\label{sec:reduction}
%
%%{\bf Gopal}: Here we should discuss how the lower bound for the path verification
%%implies a lower bound for a the random walk problem.  Just a short description how we can make a
%%random walk can be made to walk the path of length $n$ in the above constructed graph (adding enough multiple
%%edges to mimic weights). We can also point out that the same lower bound result will hold if the verification
%%is done by starting point of the random walk (rather than the root).
%
%%{\bf Danupon}: Is below enough? BTW, the path verification problem shouldn't specify that
%%the path has to be verified by the root.
%
%We now discuss how the result above implies the lower bound of the random walk problem.
%The main difference between {\sc Path-Verification} problem and the random walk problem is that in
%the former we can specify which path to verify while the latter problem generates different path each time.
%In this section we show that the ``bad'' instance ($G_n$ and $P$) in the previous section can be modified so that
%with high probability, the generated  random walk is ``hard'' to verify.
%
%\begin{theorem}
%For any $n$, there exists a graph $G_n$ of $O(n)$
%vertices and diameter $O(\log n)$, and $\ell=\Theta(n)$
%such that, with high probability, a random walk of length $\ell$ starting at $s$ needs
%$\sqrt{\frac{n}{\log n}}$ rounds to verify.
%\end{theorem}
%\begin{proof}
%First, note that Theorem~\ref{thm:mainLB} can be generalized to the case where the path $P$ has infinite
%capacity, as follows.
%
%\begin{theorem}
%\label{thm:general-LB} For any $n$, there exists a graph $G_n$ of $O(n)$
%vertices and diameter $O(\log n)$, and a path $P$ of length $\Theta(n)$
%such that any algorithm that
%solves the {\sc Path-Verification} problem on $G_n$ and $P$ requires more
%than $k$ rounds, even if edges in $P$ have large capacity (i.e., one can send larger sized messages in one step), where $k=\sqrt{\frac{n}{\log n}}$.
%\end{theorem}
%
%\begin{proof}
%This is because the proof of Theorem~\ref{thm:mainLB} only uses the congestion of edges in the tree $T$ (imposed above $P$)
%to argue about the number of rounds.
%\end{proof}
%
%Now, we modify $G_n$ to $G'_n$ as follows. Recall that the path $P$ in $G_n$ has vertices $v_1, v_2, ..., v_{n'}$.
%For each $i=1, 2, ..., n'$, we define the weight of an edge $(v_i,v_{i+1})$ to be $(2n)^{2i}$ (note that weighted
%graphs are equivalent to unweighted multigraphs in our model).
%By having more weight, these edges have more capacity as well. However, increasing capacity does not affect the claim
%in Theorem~\ref{thm:general-LB}. Observe that, when the walk is at the node $v_i$,
%the probability of walk will take the edge $(v_i,v_{i+1})$ is at least $1-\frac{1}{n^2}$. Therefore, $P$ is the resulting random
%walk with probability at least $1-1/n$. When the random walk path is $P$, it takes at least $\sqrt{\frac{n}{\log n}}$ rounds
%to verify, by Theorem~\ref{thm:general-LB}. This completes the proof.
%
%%\textbf{Danupon:} The problem with the above proof is that the weights are really huge. So, we cannot call them multiple edge.
%%One idea to fix this is to put only $2^i$ edges between $v_i$ and $v_{i+1}$ and argue that the walk will have length $\Omega(n)$ with
%%high probability. Then, we need to modify the theorem to deal with paths of length, say $n/2$, as well. Is $2^n$ small enough?
%
%%{\bf Gopal:} Why we cannot call them multiple edge (as I say in the proof above)? What is the differnece
%%if the wieght is $2^i$ as opposed to $n^i$ ?
%%{\bf Danupon:} My only worry is that $n^i$ is too much for the number of edges. (That's also true for $2^i$.)
%I%f you think it is fine then that is ok.
%
%%Another idea is to only show that with constant probability that the path will be taken.
%%Then our lower bound statement will hold with constant probability instead of high probablity.
%%In this case, we need only polynomial weights -- $n^2$ will suffice for every edge in the path. Do you agree?
%%If this is correct, we can state this also.
%\end{proof}
